#include <bits/stdc++.h>
using namespace std;

/*
1578. 使绳子变成彩色的最短时间
已解答
中等
相关标签
premium lock icon
相关企业
提示
Alice 把 n 个气球排列在一根绳子上。给你一个下标从 0 开始的字符串 colors ，其中 colors[i] 是第 i 个气球的颜色。

Alice 想要把绳子装扮成 五颜六色的 ，且她不希望两个连续的气球涂着相同的颜色，所以她喊来 Bob 帮忙。Bob 可以从绳子上移除一些气球使绳子变成 彩色 。给你一个 下标从 0 开始 的整数数组 neededTime ，其中 neededTime[i] 是 Bob 从绳子上移除第 i 个气球需要的时间（以秒为单位）。

返回 Bob 使绳子变成 彩色 需要的 最少时间 。

 

示例 1：


输入：colors = "abaac", neededTime = [1,2,3,4,5]
输出：3
解释：在上图中，'a' 是蓝色，'b' 是红色且 'c' 是绿色。
Bob 可以移除下标 2 的蓝色气球。这将花费 3 秒。
移除后，不存在两个连续的气球涂着相同的颜色。总时间 = 3 。
示例 2：


输入：colors = "abc", neededTime = [1,2,3]
输出：0
解释：绳子已经是彩色的，Bob 不需要从绳子上移除任何气球。
示例 3：


输入：colors = "aabaa", neededTime = [1,2,3,4,1]
输出：2
解释：Bob 会移除下标 0 和下标 4 处的气球。这两个气球各需要 1 秒来移除。
移除后，不存在两个连续的气球涂着相同的颜色。总时间 = 1 + 1 = 2 。
 

提示：

n == colors.length == neededTime.length
1 <= n <= 105
1 <= neededTime[i] <= 104
colors 仅由小写英文字母组成
*/

// 法一
class Solution {
public:
    int minCost(string colors, vector<int>& neededTime) {
        int n = colors.size();
        int total = 0; // 总最小移除时间
        int maxTime = neededTime[0]; // 记录当前连续同色气球的最大移除时间
        int sumTime = neededTime[0]; // 记录当前连续同色气球的移除时间总和

        // 遍历连续气球 同色连续段
        for (int i = 1; i < n; i++) {
            if (colors[i] == colors[i - 1]) {
                // 与前一个同色  add 当前连续段
                sumTime += neededTime[i];
                maxTime = max(maxTime, neededTime[i]);
            } else {
                // 不同色 计算当前连续段的最小移除时间
                total += sumTime - maxTime; // 保留最大时间的气球，其余移除
                sumTime = neededTime[i]; // 重置当前段总和
                maxTime = neededTime[i]; // 重置当前段最大时间
            }
        }
        // 处理 最后一段连续同色气球
        total += sumTime - maxTime;
        return total;
    }
};

// 法二
class Solution {
public:
    int minCost(string colors, vector<int>& neededTime) {
        int ans = 0; // 总最小删除成本
        int tmp = neededTime[0]; // 记录当前连续同色组的最大耗时
        
        // 遍历所有气球，从第二个开始对比前一个
        for (int i = 1; i < neededTime.size(); ++i) {
            if (colors[i] == colors[i-1]) { // 与前一个气球颜色相同
                // 保留耗时大的，删除耗时小的（累加成本）
                if (tmp < neededTime[i]) {
                    ans += tmp;
                    tmp = neededTime[i]; // 更新当前组最大耗时
                } else  ans += neededTime[i];                   
            } else  	tmp = neededTime[i];	// 颜色不同，开启新的连续同色组
        }
        return ans;
    }
};